//2009/07/28 12:44:55
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>

using namespace std;

class PickTeam
{
public:
    vector <string> pickPeople(int teamSize, vector <string> people)
    {
		vector<string> result;
		result.clear();
        int Max = -999999;
		int N = people.size();
        Init(people);
        for (int i=0; i<(1<<N); i++)
        {
            if (cardinality(i) == teamSize)
            {
				/*
				 * Now, once we have all a valid subset represented as an int, 
				 * we need only evaluate the score for that subset. 
				 * The simplest way to do this is with two nested loops. 
				 * Also, its useful to be familiar with bitwise operations. In particular, 
				 * the expression ((1<<j)&i)>0 will be true if and only if the jth bit of i is a one.
				 * */
                int score = 0;
                for (int j=0; j<N; j++)
                {
                    for (int k=0; k<N; k++)
                    {
                        if (((1<<j)&i) > 0 && ((1<<k)&i) > 0)
                        {
                            score += num[j][k];
                        }
                    }
                }
                if (score > Max)
                {
                    Max = score;
					result.clear();
                    for (int j=0; j<N; j++)
                    {
						if(((1<<j)&i) > 0)
							result.push_back(name[j]);
                    }
                }
            }
        }
		sort(result.begin(), result.end());
		return result;
    }

private:
    vector<vector<int> > num;
    vector<string> name;

    void Init(vector<string> p)
    {
        for (int i=0; i<p.size(); i++)
        {
            istringstream ss(p[i]);
            string s;
            ss >> s;
            name.push_back(s);
			vector<int> m;
            for (int n;ss >> n;)
            {
				m.push_back(n);
            }
			num.push_back(m);
        }
    }
    /*
	 * A good way to generate subsets is to use a bitmask. 
	 * In other words, have a single integer represent the subset, 
	 * and have the bits in that integer represent whether elements are in the subset or not. 
	 * For example, if you had the set {A,B,C}, 
	 * then the bitmask 011 (3 in decimal) could represent the subset {B,C}. 
	 * Similarly, the bitmask 101 (5 in decimal) would represent the subset {A,C}. 
	 * Using bitmasks like this allows us to iteratively generate subsets with a single for loop. 
	 * In the loop, we count from 0 (representing the empty set) up to 2n-1 (representing the entire set), 
	 * where n is the number of elements in the original set. 
	 * Every possible subset of nelements is represented by one of the number in this range. 
	 * Furthermore, the number of elements in the subset is equal to 
	 * the cardinality (number of ones in binary) of the number representing the subset. 
	 * So, we can get all of the subsets of a certain size by looking only at numbers of a certain cardinality.
	 * */
	int cardinality(int n)		//Count the number of the ones;
    {
        return n==0 ? 0 : (n&1) + cardinality(n>>1);
    }

};
